package com.adamjwh.pratice.offer;

import com.adamjwh.tools.ListNode;

/**
 * 输入两个链表，找出它们的第一个公共结点。
 */
public class FirstCommonNode {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        if (pHead1 == pHead2) {
            return  pHead1;
        }

        int len1 = getLength(pHead1);
        int len2 = getLength(pHead2);

        if (len1 < len2) {
            for (int i=0; i<len2-len1; i++) {
                pHead2 = pHead2.next;
            }
        } else {
            for (int i=0; i<len1-len2; i++) {
                pHead1 = pHead1.next;
            }
        }

        boolean flag = true;
        ListNode node = null;

        while (flag) {
            if (pHead1 == null || pHead2 == null) {
                return null;
            }

            if (pHead1 == pHead2) {
                node = pHead1;
                flag = false;
            } else {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }

        return node;
    }

    private int getLength(ListNode pHead) {
        int length = 0;
        ListNode node = pHead;

        while (node != null) {
            node = node.next;
            length ++;
        }

        return length;
    }

}
